﻿#pragma once
#include "Commond.h"
#include "ObjectPool.h"

//single-level array
template<int BITS>
class TCMalloc_PageMap1
{
private:
	static const int LENGTH = 1 << BITS;
	void** array_;

public:
	//表示页号的类型 
	typedef uintptr_t Number;

	//explicit TCMalloc_PageMap1(void* (*allocator)(size_t))
	//给array_申请空间
	explicit TCMalloc_PageMap1()
	{
		//array_ reinterpret_cast<void**>((*allocator)(sizeof(void*)<<BITS);
		size_t size = sizeof(void*) << BITS;
		size_t alignSize = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT);
		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);
		memset(array_, 0, size);
	}

	//指针找到Span*
	void* get(Number k) const
	{
		if ((k >> BITS) > 0)
		{
			return nullptr;
		}
		return array_[k];
	}

	void set(Number k, void* v)
	{
		array_[k] = v;
	}



};



//Two-level radix tree
template <int BITS>
class TCMalloc_PageMap2
{
private:
	//根节点的索引位数
	static const int ROOT_BITS = 5;
	//根节点的长度
	static const int ROOT_LENGTH = 1 << ROOT_BITS;
	//叶子节点的索引位数
	static const int LEAF_BITS = BITS - ROOT_BITS;
	//叶子节点的长度
	static const int LEAF_LENGTH = 1 << LEAF_BITS;

	//表示叶子节点，包含一个void*类型的数组
	struct Leaf
	{
		void* values[LEAF_LENGTH];
	};

	Leaf* root_[ROOT_LENGTH]; //第一层数组

	//void* (*allocator_)(size_t);

public:
	typedef uintptr_t Number;

	explicit TCMalloc_PageMap2()
	{
		//将root_数组初始化为nullptr
		memset(root_, 0, sizeof(root_));//初始化第一层空间
		//预分配内存
		PreallocateMoreMemory();//开辟第二层空间
	}

	void* get(Number k) const
	{
		//  0100 1110 0010 0000
		//& 0000 1111 1111 1111
		// -------------------- -
		//  0000 1110 0010 0000
		const Number i1 = k >> LEAF_BITS;//(0100),头位用来当作一级表
		const Number i2 = k & (LEAF_LENGTH - 1);//剩下来都为二级表，类似Linux的分级页表
		
		//页号不能小于2^BITS
		if ((k >> BITS) > 0 || root_[i1] == nullptr)
		{
			return nullptr;
		}

		return root_[i1]->values[i2];//返回该页号对应Span指针
	}

	void set(Number k, void* v)
	{
		const Number i1 = k >> LEAF_BITS;	//第一层对应下标
		const Number i2 = k & (LEAF_LENGTH - 1);	/*第二层对应下标*/

		assert(i1 < ROOT_LENGTH);
		root_[i1]->values[i2] = v; //建立该页号与对应span的映射
	}

	//确保映射【start, start->n-1】页号的空间是开辟好的
	bool Ensure(Number start, size_t n)
	{
		for (Number key = start; key <= start + n - 1;)
		{
			//计算根节点的索i1
			const Number i1 = key >> LEAF_BITS;
			if (i1 >= ROOT_LENGTH)//页号超出范围
				return false;

			if (root_[i1] == nullptr)
			{
				static ObjectPool<Leaf> leafPool;
				Leaf* leaf = (Leaf*)leafPool.New();
				//这里是*leaf,计算的大小是sizeof(void*)*LEAF_LENGTH
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}

			//计算下一个页号
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
	}

	//将两极基数数所有的可能的页号的总位数进行分配并初始化
	void PreallocateMoreMemory()
	{
		Ensure(0, 1 << BITS);//将第二层空间开辟好
	}
};

//Three level radix tree
//64位平台下使用
template <int BITS>
class TCMalloc_PageMap3
{
private:
	static const int INTERIOR_BITS = (BITS + 2) / 3; //第一，二层对应页号的比特个数
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; //第一，二层存储元素个数
	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS; //第三层对应页号的比特位数
	static const int LEAF_LENGTH = 1 << LEAF_BITS; //第三层存储的元素个数

	struct Node
	{
		Node* ptrs[INTERIOR_LENGTH];
	};

	struct Leaf
	{
		void* values[LEAF_LENGTH];
	};

	Node* NewNode()
	{
		static ObjectPool<Node> nodePool;
		Node* result = nodePool.New();
		if (result != nullptr)
		{
			memset(result, 0, sizeof(*result));
		}

		return result;
	}

	Node* root_;

public:
	typedef uintptr_t Number;

	explicit TCMalloc_PageMap3()
	{
		root_ = NewNode();
	}

	void get(Number k) const
	{
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);	//第一层对应下标
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1);//第二层对应下标
		const Number i3 = k & (LEAF_LENGTH - 1);//第三层对应下标

		//页号超出范围，或映射该页号的空间为开辟
		if ((k >> BITS) > 0 || root_->ptrs[i1] == nullptr || root_->ptrs[i1]->ptrs[i2] == nullptr)
		{
			return nullptr;
		}

		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2]->values[i3]);//返回该页号的span

	}

	void set(Number k, void* v)
	{
		assert(k >> BITS == 0);
		const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);	/*第一层对应下标*/
		const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二层对应下标
		const Number i3 = k & (LEAF_LENGTH - 1);			//第一层对应下标

		Ensure(k, 1);	//确保映射第k页页号的空间是开辟好了的
		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;//建立该页号与对应span的映射
	}

	//确保映射【start ,start->n -1】页号的空间是开辟了的
	bool Ensure(Number start, size_t n)
	{
		for (Number key = start; key <= start + n - 1;)
		{
			const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);	//第一层对应下标
			const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1);//第二层对应下标

			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)//下标超出范围
			{
				return false;
			}

			if (root_->ptrs[i1] == nullptr) //第一层i1对应下标指向的空间未开辟
			{
				//开辟对应空间
				Node* nSpace = NewNode();
				if (nSpace == nullptr)
				{
					return false;
					root_->ptrs[i1] = nSpace;
				}

			}

			if (root_->ptrs[i1]->ptrs[i2] == nullptr) //第二层ℹi2下标指向的空间未开辟
			{
				//开辟对应空间
				static ObjectPool<Leaf> leafPool;
				Leaf* leaf = leafPool.New();
				if (leaf == nullptr)
				{
					return false;
				}

				memset(leaf, 0, sizeof(*leaf));
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}

			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; //继续向后检查

		}

	}


	void preallocateMoreMemory()
	{
		Ensure(0, 1 << LEAF_BITS);//将第二层空间开辟好
	}
};
